package Hot100.Medium.GreedyAndDP.DynamicPlanning;

public class LC121_BuyStock {
    public static void main(String[] args) {

    }

    public int maxProfit(int[] prices){
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // 确定dp数组含义
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        // 初始化dp数组，显然持有股票的最大收益要初始化为买第一天的股票的负数，因为花钱了
        // 没有持有股票的最大收益证明没花钱买。也没卖，就是0
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 确定递推公式 对于持有股票的最大收益，有两个方向推出，就是i-1那天的最大收益dp[i - 1][0]
        // 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
        // 对于不持有股票的最大收益，也可以由两个状态推出来：第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
        // 或者第i天卖出股票，所得现金就是持有股票的状态下，按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[length - 1][1];
    }
}
